/**
 * 
 */
package tree.passed2;

/**
 * @author xyyi
 *
 */
public class SumRootToLeafNumbers {

	/**
	Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

	An example is the root-to-leaf path 1->2->3 which represents the number 123.

	Find the total sum of all root-to-leaf numbers.

	For example,

	1
	/ \
	2   3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.

	Return the sum = 12 + 13 = 25.
	 */
	public int sumNumbers(TreeNode root) {
		return sumNumbers(root, 0);

	}

	private int sumNumbers(TreeNode root, int sum) {
		if (root == null)
			return 0;

		sum = sum * 10 + root.val;
		// pitfall, if both left and right children are null, return sum
		if (root.left == null && root.right == null) {
			return sum;
		}

		return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public SumRootToLeafNumbers() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
